package datastructure.graph.最小生成树;

import datastructure.tree.BinaryHeap;
import datastructure.unionfind.UF;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author MaoLin Wang
 * @description
 * @date 2020/8/28 10:55 上午
 */
public class KruskalMST {
    private double weight;
    private Queue<Edge> mst;

    public KruskalMST(EdgeWeightedGraph graph) {
        BinaryHeap<Edge>heap=new BinaryHeap<>();
        for (Edge edge : graph.edges()) {
            heap.insert(edge);
        }
        UF uf=new UF(graph.V());
        mst=new LinkedList<>();

        while (!heap.isEmpty()){
            Edge edge = heap.delMin();
            int v=edge.either(), w=edge.other(v);
            if (!uf.connected(v,w)){
                mst.add(edge);
                uf.quickUnionWeight(v,w);
                weight+=edge.weight();
            }
        }
    }
    public Iterable<Edge> edges(){
        return mst;
    }
    public double weight(){
        return weight;
    }

    public static void main(String[] args) {
        EdgeWeightedGraph graph= new EdgeWeightedGraph(8);
        graph.addEdge(new Edge(4,5,0.35));
        graph.addEdge(new Edge(4,7,0.37));
        graph.addEdge(new Edge(5,7,0.28));
        graph.addEdge(new Edge(0,7,0.16));
        graph.addEdge(new Edge(1,5,0.32));
        graph.addEdge(new Edge(0,4,0.38));
        graph.addEdge(new Edge(2,3,0.17));
        graph.addEdge(new Edge(1,7,0.19));
        graph.addEdge(new Edge(0,2,0.26));
        graph.addEdge(new Edge(1,2,0.36));
        graph.addEdge(new Edge(1,3,0.29));
        graph.addEdge(new Edge(2,7,0.34));
        graph.addEdge(new Edge(6,2,0.40));
        graph.addEdge(new Edge(3,6,0.52));
        graph.addEdge(new Edge(6,0,0.58));
        graph.addEdge(new Edge(6,4,0.93));
        KruskalMST kruskalMST=new KruskalMST(graph);
        System.out.println(kruskalMST.weight);
    }
}
